package jianzhioffer.bit;

import java.util.Arrays;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 数组中只出现一次的数字
 * 描述：给一个数组，数组里除了两个数字之外，其他的都是成对出现的数字。找出这两个数字
 * 思路：异或。两个相同的数字异或之后结果为0
 * Created by yzy on 2019-11-28 15:38
 */
public class FindNumsAppearOnce {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5,7,5,4,3,2,1,6,8,8};
        int[] num1 = new int[1];
        int[] num2 = new int[1];
        findNumsAppearOnce(arr,num1,num2);
        System.out.println(num1[0] + "---" + num2[0]);

        ConcurrentHashMap map = new ConcurrentHashMap();
        map.clear();
    }

    public static void findNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        if(array.length < 2){
            return;
        }

        int res = Arrays.stream(array).reduce((a,b) -> a^b).getAsInt();
        int indexOfOne = findIndexOfOne(res);
        num1[0] = 0;
        num2[0] = 0;
        for(int n : array){
            if(isIndexIsOne(n, indexOfOne)){
                num1[0] = num1[0] ^ n;
            }else{
                num2[0] = num2[0] ^ n;
            }
        }
    }

    private static int findIndexOfOne(int num){
        int idx = 0;
        while((num & 1)==0 && idx < 32){
            num = num >> 1;
            idx++;
        }
        return idx;
    }

    private static boolean isIndexIsOne(int num, int index){
        int tmp = num >> index;
        return (tmp & 1)==1;
    }
}
